Data processing systems, including microprocessors, may use queues for temporarily storing information prior to being transferred to some other resource in the system. Each queue comprises a series of registers of suitable width for the information which they are to store temporarily. Each register represents a location in the queue. The information which may be stored in a queue location may comprise memory address information, data, or control information. Regardless of the number of locations in a particular queue and the width of each location, some mechanism must be associated with the queue for selecting a particular location so that the information stored in that location may be transferred to another resource in the system.
A queue may be operated to shift the stored information from one queue location to the next. This shifting operation may be used to control how the stored information is transferred from the queue to the next resource in the system. For example, queue entries may shift down through the locations in a queue, with each entry moving to the next location in the queue on the occurrence of an event such as a clock cycle. Upon the occurrence of each event, the entry in the last queue location exits the queue and the first queue location receives a new queue entry. Alternatively, a queue may be operated to hold information in a single location until the information is selected to be transferred to another resource in the system. These static queues must include some mechanism by which a particular queue location may be selected.
A queue may be used in a data processing system to hold address, data, and control information associated with a number of outstanding or pending store transactions. Store transactions which may be held in the queue include write-through stores, pushes, interventions, castouts, cache control operations, and barrier instructions.
Referring still to the store example, it is desirable to prioritize transactions in the queue to ensure that certain transactions are transferred on for processing earlier than other transactions which may have been stored in the queue. A castout transaction from one processor, for example, is preferably transferred from the queue more quickly when another processor requests the information stored at the address specified by the castout transaction. It is also desirable to eliminate certain transactions from the queue to prevent the transactions from being passed on to the next processing step. For example, where a castout transaction is to be stored in the queue specifies an address which is the same address as that specified in an older castout transaction already resident in the queue, in this case the older transaction represents a transaction with stale data. It is, therefore, desirable to remove such a castout transaction from the queue in order to prevent the transaction from being finished unnecessarily only to be overwritten by the newer castout transaction.
Prior data processing systems have used a priority bit in each queue location to differentiate between the priorities of different transactions in the queue. Arbitration logic associated with these systems used the priority bits to schedule the transactions for transfer from the queue. However, the larger the queue, the more complex the arbitration logic required to implement a priority bit scheme.
A store transaction queue may be implemented as a dynamic queue in which transactions shift from one location to the next in each clock cycle or other event. However, shifting large amounts of data in the queue causes power dissipation and does not facilitate prioritization of transactions in the queue.